package algorithm.niuke;

public class 统计不同回文子字符串 {
    /*
     * 给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并返回该数字与 10^9 + 7 的模。
     * 
     * 通过从 S 中删除 0 个或多个字符来获得子字符序列。
     * 
     * 如果一个字符序列与它反转后的字符序列一致，那么它是回文字符序列。
     * 
     * 如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。
     * 
     * 
     * 
     * 示例 1：
     * 
     * 输入： S = 'bbccbb' 输出：10 解释： 10 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb',
     * 'bccb','bbbb','bbcbb',。 注意：'bcb' 虽然出现两次但仅计数一次。 示例 2：
     * 
     * 输入： S =
     * 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
     * 输出：104860361 解释： 共有 3104860382 个不同的非空回文子字符序列，对 10^9 + 7 取模为 104860361。
     * 
     * 
     * 提示：
     * 
     * 字符串 S 的长度将在[1, 1000]范围内。 每个字符 S[i] 将会是集合 {'a', 'b', 'c', 'd'} 中的某一个。
     */
    public int countPalindromicSubsequences(String S) {
        /*
         * 思路：如果Si=Sj,那么Si和Sj就可以作为回文串的最2端，其中对i<k<j中的形成的回文串，加上Si，Sj也一定是回文串
         */
        int len = S.length();
        int[][] count = new int[len + 2][len + 2];
        return 0;
    }
}
